The present invention relates to a method of comparing multiple-bit input signals, and a multiple-bit comparator that can be used in, for example, a content-addressable memory such as a cache memory.
A multiple-bit comparator receives a pair of multiple-bit input signals, and generates an output signal that indicates whether the two input signals are mutually identical in every bit. In a cache memory, one of the input signals gives the address of a desired data word, and the other input signal gives the address of a cached data word. The output signal indicates whether the two addresses are the same, resulting in what is termed a cache hit, or whether they are not the same, resulting what is termed in a cache miss.
The classic circuit configuration of a multiple-bit comparator, which will be illustrated later, comprises a plurality of exclusive OR gates that compare the individual bits of the two input signals, and a NOR gate that combines the outputs of the exclusive OR gates to generate the final output signal. This configuration works well only when the number of input bits is small. When there are many bits, it becomes difficult to design the NOR gate without encountering such problems as excessive gate propagation delay, excessive circuit layout space, and excessive power dissipation.
To avoid these problems, Japanese Patent Kokai Application No. 252706/1986 discloses a multiple-bit comparator in which the exclusive OR gates have an open-drain output structure, and are coupled in a wired-OR configuration to a sense amplifier. Japanese Patent Kokai Application No. 75748/1994 discloses a multiple-bit comparator in which the exclusive OR gates drive respective pull-up transistors, which are coupled in a wired-OR configuration to an output terminal that is pre-charged to the ground level. The output signals of both of these multiple-bit comparators are normally in the state denoting mutually identical input signals. When the input signals are not identical, the output timing therefore varies depending on the number of non-matching bits, creating problems in timing design.
A further problem, not addressed by any of the above prior art, is that of false output signals, referred to as hazards, that may occur when one or both of the input signals are invalid. In a cache memory, such hazards can cause memory control circuits to malfunction, or cause the wrong data to be accessed. Such hazards also create timing design difficulties, because it becomes necessary to ensure that the output signal is sampled at a point that avoids the hazards, as far as possible.